iOS 9.3.5 bluetooth not working

Try holding down the Home and Wake/Sleep buttons at the same time for about 15 seconds until the Apple logo appears. You will not lose anything.

If a restart does not help try a System Restore. First backup your device using iTunes. Also import your photos to your computer and copy all important data if possible. Try restoring from backup first and testing it. If it does not help, you may have to restore as New and reconfigure from scratch as the backup could be corrupted. For this reason it is important to have your photos and data saved separately from the backup. Here are the steps for a Restore:

https://support.apple.com/en-us/HT201252

If the above steps do not help, you may have to have it tested at an Apple store.

I am experiencing this problem as well (iPhone 5, 64GB, upgraded from 9.3.4).

Each incremental upgrade in the 9.0 branch was either better or worse than the last. Now, on 9.3.5... this is the absolute worst!
Symptoms after upgrading to 9.3.5

• Suspected greater battery drain (difficult to prove b/c I didn't bench mark before) but I am now losing about x % per hour. I'll input a value once I measure it.
• Bluetooth failure. So far, my MS Band 2 no longer pairs (get pairing errors when/if it is found). Two other Bluetooth devices are no longer even found.
• Worse and stranger BT failure. My beloved and expensive Plantronics Back Beat Sense headphones will pair but I no longer hear any sound, nor can I control pause, forward, back. This fault discovery assures me that the Apple 9.3.5 is definitely the culprit.

Troubleshooting
All the usual

• Power down (multiple times)
• Reset (power button/home button) - Actually, the phone will do its own resets (sometimes once per day and usually while browsing with Safari). So yes, multiple times! 😟
• Inside Bluetooth - clicking and selecting Forget This Device. Doing so, means that the device will no longer be found. Of course, that is not normal!

To Do - Next?

Hard reset to factory and reinstall iOS. But my concern is that this will be a waste of time if, in fact, 9.3.5 is the problem and it's not a slightly faulty install.

Hi

When you try to pair for the first time it can take up to 10 minutes

I had the same problem with at bose soundlink but after first time it now pairs quick .

Just leave to pair for up to 10 minutes .

Cheers

Brian

downgrade fixed bluetooth, and reverified upgrade from 9.3.5 broke it. Rang apple support twice said they would call me back with solution. Took it into the store and it was past the 90 day warranty they gave me on the phone and wanted $300 for same model replacement. Net effect was over 4 hours of dialog with apple and no solution.

iPhone 5 is permanently bluetooth disabled by latest firmware.

i am having the same problem-contacted apple support, they tried to tell me it was hardware issues-its NOT

before updating-my bluetooth worked perfect & of course we arent allowed to downgrade